// 算法过程理解视频:https://www.bilibili.com/video/BV1Dv4y147ai/?spm_id_from=333.337.search-card.all.click&vd_source=a0d54f8f715d4d2f9264bf66f84bcee7
// 本质上还是插入排序,只不过先分组,组内分别执行插入排序;然后增量不断减小,直到所有元素在同一个组;
// 组内有序之后,再对整体做一遍插入排序;
// 希尔排序正是利用了插入排序的两个优势

#include <iostream>
#include <vector>
using namespace std;

void ShellSort(vector<int> &arr)
{
    int increment = arr.size(); // 增量初始化;
    int temp;
    int j;
    // increment会不断减小,直到=1;=1时走一遍基本的插入排序之后序列就是有序的了;
    // 此处可以替换成do while循环,先做循环再判断,从而保证increment=1时能够走一遍插入排序
    while (increment >= 1)
    {
        // 对于整数除法，结果将是整数,即向下取整;increment=1表示整个序列为一个组
        increment = increment / 3 + 1; // 一般是这样改变增量;若increment=1则会一直保持为1
        // 下面就要在每个组内做插入排序;但是不是一个组做完再做另一个组,而是借助increment轮流给每个组做
        for (int i = increment; i < arr.size(); i++)
        {
            // 这个循环全部执行完之后意味着当前分组下,每个组内都是有序的了
            // i = increment为初始值是因为:每个组内都是做的插入排序,二插入排序是把第一个元素作为有序的;
            // 因此需要跳过每个组的第一个元素
            if (arr[i] < arr[i - increment])
            {
                // 即如果组内第二个元素比组内前一个元素小,则应该执行插入排序
                temp = arr[i];
                for (j = i - increment; j >= 0 && arr[j] > temp; j = j - increment)
                {
                    // 注意步长是j=j-increment,而不是j--
                    arr[j + increment] = arr[j]; // 大的元素要后移
                }
                arr[j + increment] = temp;
            }
        }
        if (increment == 1)
        {
            // 循环结束才break保证increment=1时遍历过一次才结束
            break;
        }
    }
}

int main()
{
    vector<int> arr = {4, 3, 99, 3, 9};
    for (int i = 0; i < arr.size(); i++)
    {
        cout << arr[i] << ",";
    }
    cout << endl;
    ShellSort(arr);
    for (int i = 0; i < arr.size(); i++)
    {
        cout << arr[i] << ",";
    }

    return 0;
    
}